package _11_二叉树的前中后非递归遍历.tree;

import java.util.Comparator;

/*
    二叉搜索树 元素必须具备可比较性
 */
public class BST<E> extends BinaryTree<E> {
    private Comparator<E> comparator; //支持元素可比较性

    public BST() {
        this(null);
    }

    public BST(Comparator<E> comparator) {
        this.comparator = comparator;
    }

    //添加元素
    public void add(E element){
        elementNotNullCheck(element);

        //添加的第一个节点 根节点
        if(root == null){
            root = createNode(element,null);
            size++;
            //添加之后进行调整
            afterAdd(root);
            return;
        }

        //添加的不是第一个节点
        Node<E> node = root; //从根节点开始比较
        Node<E> parent = root; //记录父节点
        int cmp = 0; //记录比较结果
        while(node != null){
            cmp = compare(element,node.element); //每一轮进行比较
            parent = node; //记录父节点
            if(cmp > 0){
                node = node.right;
            }else if(cmp < 0){
                node = node.left;
            }else{ //相等的情况
                node.element = element; //直接覆盖即可
                return;
            }
        }

        Node<E> newNode = createNode(element,parent);
        //根据方向进行插入节点
        if(cmp > 0){
            parent.right = newNode;
        }else{
            parent.left = newNode;
        }
        size++;

        //添加之后进行调整
        afterAdd(newNode);


    }

    /**
     * BST给AVL和 RBTree提供的接口，交给他们去重写，用于添加节点以后的自平衡调整，
     * BST本身没有自平衡的特性，所以空实现
     * @param node 新添加的节点
     */
    protected void afterAdd(Node<E> node){

    }

    /**
     * BST给AVL和 RBTree提供的接口，交给他们去重写，用于删除节点以后的自平衡调整，
     * BST本身没有自平衡的特性，所以空实现
     * @param node 待删除的节点或者用以取代被删除的节点(当被删除的节点度为1时)
     */
    protected void afterRemove(Node<E> node){

    }

    //删除节点
    public void remove(E element){
        remove(node(element));
    }

    //删除节点
    private void remove(Node<E> node){
        if(node == null) return;
        size--;

        //首先考虑删除度为2的节点，找到其前驱节点或者后继节点，将其转换为删除度为1或者度为0的节点
        if(node.hasTwoKids()){
            Node<E> pre = predecessor(node);
            node.element = pre.element;
            node = pre; //下面统一进行处理
        }

        //删除度为1或者度为0的节点
        Node<E> replacement = node.left != null ? node.left : node.right;
        if(replacement != null){ //删除度为1的节点
            replacement.parent = node.parent;
            if(node.parent == null){ //删除度为1的根节点
                root = replacement;
            } else if(node.isLeftChild()){
                node.parent.left = replacement;
            }else{
                node.parent.right = replacement;
            }
            //删除度为1的节点以后的调整
            afterRemove(replacement);
        }else if(node.parent == null){ //删除度为0的根节点
            root = null;
            //删除度为0的根节点以后的调整
            afterRemove(node);
        }else{ //删除度为0的叶子节点
            if(node.isLeftChild()){
                node.parent.left = null;
            }else{
                node.parent.right = null;
            }
            //删除度为0的叶子节点以后的调整
            afterRemove(node);
        }

    }

    //根据元素找到元素所在节点
    private Node<E> node(E element){
        elementNotNullCheck(element);
        Node<E> node = root;
        while (node != null){
            int cmp = compare(element,node.element);
            if(cmp == 0) return node;
            if(cmp > 0){
                node = node.right;
            }else{
                node = node.left;
            }
        }
        return null;
    }

    //是否包含某个元素
    public boolean contains(E element){
        return node(element) != null;
    }

    //内部比较方法
    private int compare(E e1,E e2){
        //如果该BST实现了comparator接口，那么内部比较方法就是用比较器
        if(comparator != null){
            return comparator.compare(e1, e2);
        }
        //否则就强制转换成自然排序接口进行比较
        return ((Comparable<E>)e1).compareTo(e2);
    }

    //检测元素内部不能为null
    protected void elementNotNullCheck(E element){
        if(element == null){
            throw new IllegalArgumentException("元素不能为null");
        }
    }
}
